#ifndef RBTREEITERATOR_H_INCLUDED
#define RBTREEITERATOR_H_INCLUDED
#include "RBTreeNode.h"
/**
 * 红黑树迭代器
 */
template<typename K, typename V>
class RBTreeIterator
{
    typedef RBTreeNode<K, V> Node;

    typedef Node *ParentNode;

    typedef RBTreeIterator<K, V> Self;

public:
    RBTreeIterator(const Self & s);

    RBTreeIterator(ParentNode parentNode = nullptr): pNode(parentNode)
    {

    }

    inline ParentNode getParentNode() const
    {
        return this->pNode;
    }

    std::pair<K, V> operator *();

    std::pair<K, V> operator ->();

    bool operator!=(const Self& s);

    Self operator++();


private:
    ParentNode pNode;

    // 增量
    void increment();

    // 递减量

    void decrement();
};

template<typename K, typename V>
RBTreeIterator<K, V>::RBTreeIterator(const RBTreeIterator::Self & s):pNode(s.pNode)
{

}

template<typename K, typename V>
std::pair<K, V> RBTreeIterator<K, V>::operator*()
{
    return this->pNode->value;
}

template<typename K, typename V>
std::pair<K, V> RBTreeIterator<K, V>::operator ->()
{
    return & (operator*());
}

template<typename K, typename V>
void RBTreeIterator<K, V>::increment()
{
    if (this->pNode->reight)
    {
        this->pNode = this->pNode->reight;
        while (this->pNode->left)
            this->pNode = this->pNode->left;
    }
    else
    {
        ParentNode pParent = this->pNode->parent;
        while (pParent->reight == this->pNode)
        {
            this->pNode = pParent;
            pParent = this->pNode->parent;
        }

        // 如果树的根节点没有右孩子的情况且迭代器起始位置在根节点
        if (this->pNode->reight != pParent)
            this->pNode = pParent;
    }
}


template<typename K, typename V>
void RBTreeIterator<K, V>::decrement()
{
    if (this->pNode->parent->parent == this->pNode && RED == this->pNode->color)
    {
        this->pNode = this->pNode->reight;
    }
    else if (this->pNode->left)
    {
        // 在当前节点左子树中找最大的结点
        this->pNode = this->pNode->left;
        while (this->pNode->reight)
            this->pNode = this->pNode->reight;
    }
    else
    {
        ParentNode pParent = this->pNode;
        while (pParent->left == this->pNode)
        {
            this->pNode = pParent;
            pParent = this->pNode->parent;
        }

        this->pNode = pParent;
    }
}
template<typename K, typename V>
bool RBTreeIterator<K, V>::operator!=(const Self& s)
{
    return this->pNode != s.pNode;
}

template<typename K, typename V>
typename RBTreeIterator<K, V>::Self RBTreeIterator<K, V>::operator++()
{
    this->increment();

    return *this;
}
#endif // RBTREEITERATOR_H_INCLUDED
